package sort.basic_sort;

import java.util.Arrays;

/**
 * @author dx
 * @version 1.0
 * @date 2022/4/18 10:07
 * @description:
 */
public class quickSort {

    public static  void main(String[] args){
        int [] test = {1,3,2,4,9,3,1,6,12,13,16,9,0};
        quickSort(test,0,test.length-1);
    }
    public static void quickSort(int[] arr,int low,int high){
        if(arr.length<=0) return;
        if(low>=high) return;
        int left = low;
        int right = high;

        int temp = arr[left];   //挖坑1  保存基准的值
        while(left<right){
            while(left<right && arr[right]>=temp){
                right--;
            }
            arr[left] = arr[right];  //坑2 从后往前找到比基准小的元素，放到坑1
            while (left<right && arr[left]<=temp){
                left++;
            }
            arr[right] = arr[left]; //坑3  从前往后找到比基准大的元素，放到刚才挖的坑2中
        }
        arr[left] = temp;
        System.out.println("Sorting: " + Arrays.toString(arr));
        quickSort(arr, low, left-1);
        quickSort(arr, left+1, high);
    }
}
